0% completed
Problem Statement
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
Each combination must be a unique set of numbers, order of which does not matter.
Examples
-
Example 1:
- Input:
n = 3, k = 2 - Expected Output:
[[1, 2], [1, 3], [2, 3]] - Justification:
[[1, 2], [1, 3], [2, 3]]are all combinations of size 2, which we can create using[1, 2, 3].
- Input:
-
Example 2:
- Input:
n = 4, k = 1 - Expected Output:
[[1], [2], [3], [4]] - Justification:
[[1], [2], [3], [4]]are all combinations of size 1, which we can create using `[1, 2, 3, 4].
- Input:
-
Example 3:
- Input:
n = 5, k = 3 - Expected Output:
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]] - Justification: We unique triplets using numbers 1 to 5, yielding ten different combinations.
- Input:
Solution
To solve this problem, we can employ a backtracking approach. Backtracking is a recursive strategy for solving problems by exploring all possible solutions and backtrack whenever a solution that's currently being explored no longer seems viable. This approach is particularly effective for generating combinations because it allows us to build combinations one element at a time and backtrack as soon as we've either found a valid combination or need to make a different choice to continue exploring possibilities.
Backtracking works here by choosing a start number for a combination, then recursively choosing the next number, ensuring each number is greater than the previous to maintain uniqueness and avoid duplication. This method efficiently explores all potential combinations of k numbers within the given range, ensuring no possibilities are missed and no invalid combinations are included.
Step-by-step Algorithm
- Initialize an empty list (or array)
resultto store all the combinations. - Define a helper function
backtrackthat takes the current combination (tempList), the starting number (start), 3.n, andkas parameters. Begin the process by callingbacktrackwith an emptytempList,startas 1,n, andk. - Check if the current combination's size equals
k. If so, add a copy oftempListtoresultand return. - Iterate from the current
startnumber ton:- Add the current number
itotempList. - Recursively call
backtrackwithi + 1as the newstart, to ensure each combination is unique and respects the ascending order. - Remove the last number added to
tempListto backtrack, exploring other possible combinations by trying the next number in the sequence.
- Add the current number
- Once all combinations are explored, return the
result.
Algorithm Walkthrough
Let's consider the input n = 5 and k = 3:
- Initialize
resultas an empty list to store combinations. - Call
backtrackwith an empty list astempList,start = 1,n = 5, andk = 3. - First Call to Backtrack:
tempList = [],start = 1- Loop from
i = 1to5:- Add
1totempListand callbacktrackwithstart = 2.- Second Call to Backtrack:
tempList = [1],start = 2- Loop from
i = 2to5:- Add
2totempListand callbacktrackwithstart = 3.- Third Call to Backtrack:
tempList = [1, 2],start = 3- Loop from
i = 3to5:- Add
3totempListmaking it[1, 2, 3]and sincetempList.size() == k, add[1, 2, 3]toresult. - Backtrack: Remove
3, makingtempList = [1, 2]. - Add
4totempListmaking it[1, 2, 4]and sincetempList.size() == k, add[1, 2, 4]toresult. - Backtrack: Remove
4, makingtempList = [1, 2]. - Add
5totempListmaking it[1, 2, 5]and sincetempList.size() == k, add[1, 2, 5]toresult. - Backtrack: Remove
5, makingtempList = [1, 2].
- Add
- Backtrack to the second call:
tempList = [1].
- Third Call to Backtrack:
- Next,
i = 3in the second call, add3totempListmaking it[1, 3]and proceed similarly. - Continue this process until all combinations starting with
1are explored.
- Add
- Second Call to Backtrack:
- Backtrack and try next numbers as the starting point,
[2, 3, 4],[2, 3, 5],[2, 4, 5],[3, 4, 5]will be generated in subsequent calls.
- Add
- After exploring all possible combinations starting from
1to5, theresultwill contain all unique combinations of size3from numbers1to5. - Return
resultwhich now holds all the required combinations:[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]].
Code
Complexity Analysis
Time Complexity
: The primary factor affecting the time complexity is the number of combinations generated, denoted as C(n, k), whereC(n, k)is the binomial coefficient representing the number of ways to choose k elements out of n options. For each combination, we perform operations that are proportional to k (to add elements to a temporary list or array). Therefore, the total time complexity is.
Space Complexity
: The space required to store all combinations is directly proportional to the number of combinations times the size of each combination, which is k. This accounts for the space needed to store the output.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity